package _1081_Smallest_Subsequence_of_Distinct_Characters;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * Date: 2020/12/2 16:35
 * Content: 单调栈
 * https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/
 *
 * 执行用时：4 ms, 在所有 Java 提交中击败了64.13%的用户
 * 内存消耗：36.7 MB, 在所有 Java 提交中击败了64.20%的用户
 */
public class Solution {

    public String smallestSubsequence(String s) {

        if (s.length() <= 1) return s;

        // 第一步：统计各个小写字母出现的次数
        int[] f = new int[26];
        for (char c : s.toCharArray()) f[c - 'a']++;

        // 第二步：通过单调栈解决
        Deque<Character> stk = new ArrayDeque<>();  // 单调栈，不是完全单调的，因为要保证字符串中的字母至少出现一次
        HashSet<Character> S = new HashSet<>();  // set中存储着stack存在的小写字母
        for (char c : s.toCharArray()) {
            if (!S.contains(c)) {
                while (!stk.isEmpty() && c < stk.peek() && f[stk.peek() - 'a'] > 0) S.remove(stk.pop());
                S.add(c);
                stk.push(c);
            }
            f[c - 'a']--;
        }

        // 第三步：得到结果
        StringBuilder sb = new StringBuilder();
        while (!stk.isEmpty()) sb.append(stk.pop());

        return sb.reverse().toString();
    }

    public static void main(String[] args) {

        System.out.println((new Solution()).smallestSubsequence("cbacdcbc"));
    }
}
